package ArrayList;

import org.junit.Test;

import java.util.Arrays;

/**
 * @Classname JZ53
 * @Description TODO
 * @Date 2022/12/8 11:24
 * @Created by xjl
 */
public class JZ53在排序数组中查找数字 {

    /**
     * @description 查询目标的数字在的次数
     * @param: nums
     * @param: target
     * @date: 2022/12/8 11:25
     * @return: int
     * @author: xjl
     */
    public int search(int[] nums, int target) {
        int count = 0;
        for (int i : nums) {
            if (i == target) {
                count++;
            }
        }
        return count;
    }

    /**
     * @description 利用数组有序 利用二分查找的 log(n)  空间是 O(0)
     * @param: nums
     * @param: target
     * @date: 2022/12/8 11:27
     * @return: int
     * @author: xjl
     */
    public int search2(int[] nums, int target) {
        int count = 0;
        int index = Arrays.binarySearch(nums, target);
        if (index < 0) {
            return 0;
        } else {
            int left = index - 1;
            while (left >= 0) {
                if (nums[left] == target) {
                    count++;
                    left--;
                } else {
                    break;
                }
            }
            int right = index + 1;
            while (right < nums.length) {
                if (nums[right] == target) {
                    count++;
                    right++;
                } else {
                    break;
                }

            }
            return count + 1;
        }
    }

    public int search3(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int firstposition = findFirstPostition(nums, target);
        if (firstposition == -1) {
            return 0;
        }
        int lastposition = findLastPostition(nums, target);
        System.out.println(firstposition);
        System.out.println(lastposition);
        return lastposition - firstposition + 1;
    }

    private int findLastPostition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left+(right-left+1)/2;
            if (nums[mid] <= target) {
                left = mid;
            } else {
                right = mid-1;
            }
        }
        return left;
    }

    private int findFirstPostition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left+(right-left)/2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (nums[left] == target) {
            return left;
        }
        return -1;
    }

    @Test
    public void test() {
        int i = search3(new int[]{5, 7, 7, 8, 8, 10}, 8);
        System.out.println(i);
    }
}
